// NC14 按之字形顺序打印二叉树 https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0
//  层次遍历+双端队列
//  ArrayList = vector
//  Deque  =  deque 代替stack
// LinkedList

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public ArrayList Print(TreeNode pRoot) {
    Deque<TreeNode> deque = new LinkedList<>();
    ArrayList res = new ArrayList<>();
    if(pRoot != null)
        deque.add(pRoot);
    while(!deque.isEmpty()) {
        // 打印奇数层
        ArrayList tmp = new ArrayList<>();
        for(int i = deque.size(); i > 0; i--) {
            // 从左向右打印
            TreeNode node = deque.removeFirst();
            tmp.add(node.val);
            // 先左后右加入下层节点
            if(node.left != null) deque.addLast(node.left);
            if(node.right != null) deque.addLast(node.right);
        }
        res.add(tmp);
        if(deque.isEmpty()) break; // 若为空则提前跳出
        // 打印偶数层
        tmp = new ArrayList<>();
        for(int i = deque.size(); i > 0; i--) {
            // 从右向左打印
            TreeNode node = deque.removeLast();
            tmp.add(node.val);
            // 先右后左加入下层节点
            if(node.right != null) deque.addFirst(node.right);
            if(node.left != null) deque.addFirst(node.left);
        }
        res.add(tmp);
    }
    return res;
}
